class Solution
{
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>> &paths)
    {
        vector<int> type(n, 0);
        vector<vector<int>> adjTable(n);
        for (auto &path : paths)
        {
            adjTable[path[0] - 1].push_back(path[1] - 1);
            adjTable[path[1] - 1].push_back(path[0] - 1);
        }

        for (int i = 0; i < n; ++i)
        {
            int used = 0;
            for (int near : adjTable[i])
            {
                used |= 1 << type[near];
            }
            for (int thisType = 1; thisType <= 4; ++thisType)
            {
                if (!(used & (1 << thisType)))
                {
                    type[i] = thisType;
                    break;
                }
            }
        }
        return type;
    }
};